#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MVNum = 6;
typedef string VerTexType;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;

} ArcNode;
typedef struct VNode
{
    VerTexType data;
    ArcNode *firstarc;

} VNode, AdjList[MVNum];

typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

struct QueueNode
{
    int val;
    struct QueueNode *next;
    QueueNode()
    {
        next = NULL;
    }
}; 
struct Queue
{
    QueueNode *head;
    QueueNode *tail;
    Queue()
    {
        head = NULL;
        tail = NULL;
    }
};
 void InitQueue(Queue &Q)
{
}
void EnQueue(Queue &Q, int v)
{
    
    QueueNode *tmp = new QueueNode();
    tmp->val = v;
    if (Q.tail == NULL){
        Q.tail = tmp;
    }
    if (Q.head == NULL){
        Q.head = tmp;
    }
    if (Q.head != NULL && Q.tail != NULL){
        Q.tail->next = tmp;
        Q.tail = tmp;
    }
}

bool QueueEmpty(Queue &Q)
{
    return Q.head == NULL and Q.tail == NULL;
}

void DeQueue(Queue &Q, int &i)
{
    if (Q.head == Q.tail){
        Q.tail = NULL;
    }
    i = Q.head->val;
    QueueNode *dp = Q.head;
    Q.head = Q.head->next;

    delete dp;
    
}

#define TRUE 1
#define FALSE 0
int visited[MVNum];
void BFS(ALGraph &G, int v)
{
    Queue Q;
    cout << G.vertices[v].data;
    visited[v] = TRUE;
    EnQueue(Q, v);
    while (!QueueEmpty(Q))
    {
        int i;
        DeQueue(Q, i);
        ArcNode *p = G.vertices[i].firstarc;
        while (p != NULL)
        {
            int w = p->adjvex;
            if (!visited[w])
            {
                cout << G.vertices[w].data;
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
            p = p->nextarc;
        }
    }
}



void create(ALGraph &G){
    string ds[MVNum] = {"A", "B", "C", "D", "E", "F"};
    vector<vector<int>> vec = {
        {1,4},
        {0,4,5},
        {3,5},
        {2,5},
        {0,1},
        {1,2,3}
    };
    
    for (int i = 0; i < MVNum; i ++){
        G.vertices[i] = *(new VNode());
        G.vertices[i].data = ds[i];
        G.vertices[i].firstarc = NULL;
        for (int j = vec[i].size() - 1; j >= 0; j --){
            ArcNode *tp = new ArcNode();
            
            tp->adjvex = vec[i][j];
            tp->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = tp;
        }

        
    }

}

int main(int argc, char const *argv[])
{
    ALGraph G;
    create(G);
    for (int i = 0; i < MVNum; i ++){
        visited[i] = 0;
    }
    BFS(G, 0);

    return 0;
}

